package B刷题.B链表问题;

/**
 * @author wei.zhao
 * @description: 程序员代码面试指南：删除链表的中间节点和a/b处的节点
 * @date 2022/12/14 16:27
 */
public class Code03_删除链表的中间节点和ab处的节点 {

    /**
     * 思路：
     * 找到中间节点的前一个节点，该节点next指向下下个节点；
     * 不需要遍历链表两次，找中间节点--->快慢指针，找中间节点的前一个节点--->快指针先走一次；
     * 注意：中间节点的前一个节点为空的情况，即链表长度为0、1、2
     */
    public Node removeMidNode(Node head) {
        if (head == null || head.next == null) {
            return null;
        }
        if (head.next.next == null) {
            return head.next;
        }
        Node fast = head.next.next;
        Node preNode = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            preNode = preNode.next;
        }
        preNode.next = preNode.next.next;
        return head;
    }

    /**
     * 思路：
     * 求该节点索引位，该节点的前一个节点的next指向next.next；
     */
    public Node removeByRatio(Node head, int a, int b) {
        // 计算链表长度
        Node cur = head;
        int length = 0;
        while (cur != null) {
            length++;
            cur = cur.next;
        }
        // 计算删除的位
        int del = (int) Math.ceil((double) length * a / (double) b);
        if (del == 0 || del > length) {
            return head;
        } else if (del == 1) {
            return head.next;
        } else {
            cur = head;
            int i = 1;
            while (i != del - 1) {
                cur = cur.next;
                i++;
            }
            cur.next=cur.next.next;
        }
        return head;
    }
}
